// 多源 bfs 问题
// 把多个源点当成一个超级源点 - 即将所有源点加入队列中，之后进行 bfs 搜索
// 正难则反 - 如果不容易按照题意直接解决，可以从反方向入手

// 例题 2：
// 给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
// 一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
// 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
//
//        示例 1：
//
//
//        输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
//        输出：3
//        解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
//        示例 2：
//
//
//        输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
//        输出：0
//        解释：所有 1 都在边界上或可以到达边界。
//
//
//        提示：
//
//        m == grid.length
//        n == grid[i].length
//        1 <= m, n <= 500
//        grid[i][j] 的值为 0 或 1

// 解题思路：
// 正难则反 - 将所有的 1 的坐标加入队列
// 进行多源 bfs 搜索，扩展到的位置标上距离
// 可以通过 check[i][j] 进行标记能搜索到的 1 的坐标
// 返回没有标记的 1 的坐标的个数

import java.util.LinkedList;
import java.util.Queue;

public class NumEnclaves {
    public int numEnclaves(int[][] grid) {
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] check = new boolean[m][n];
        for(int j = 0; j < n; j++){
            if(grid[0][j] == 1){
                queue.offer(new int[] {0, j});
                check[0][j] = true;
            }
            if(grid[m - 1][j] == 1){
                queue.offer(new int[] {m - 1, j});
                check[m - 1][j] = true;
            }
        }
        for(int i = 0; i < m; i++){
            if(grid[i][0] == 1){
                queue.offer(new int[] {i, 0});
                check[i][0] = true;
            }
            if(grid[i][n - 1] == 1){
                queue.offer(new int[] {i, n - 1});
                check[i][n - 1] = true;
            }
        }
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            int a = point[0];
            int b = point[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && check[x][y] == false){
                    queue.offer(new int[] {x, y});
                    check[x][y] = true;
                }
            }
        }
        int ret = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1 && check[i][j] == false) ret++;
            }
        }
        return ret;
    }
}
